1101C - Division and Union - CodeForces Solution

//      بسم الله الرحمن الرحيم
//      All praise is due to ALLAH alone
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define go continue
#define exit return 0
#define ll long long int
#define ull unsigned long long int
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define print_vec(vec) for(int i=0;i<vec.size();i++)cout<<vec[i]<<' ';
#define print_set(st) for(auto it=st.begin();it!=st.end();it++)cout<<*it<<' ';
#define print_pair(vec) for(int i=0;i<vec.size();i++)cout<<vec[i].first<<' '<<vec[i].second<<endl;
#define dbg(num) cerr<< "Line "<<__LINE__ <<": "<< #num <<" = "<<(num)<<endl
//int dx[]={-2, -2, -1, -1,  1,  1,  2,  2};
//int dy[]={-1,  1, -2,  2, -2,  2, -1,  1};
int dx[] = { -1, 0, +1, 0};
int dy[] = {0, +1, 0, -1};
#define mod 1000000007
#define sz 1000000
struct query {
	int l;
	int r;
	int id;
};
query qr[sz + 1];
bool cmp(query a, query b)
{
	if (a.l == b.l)
		return a.r > b.r;
	else return a.l < b.l;
}
int main()
{
	fast;
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			int l1, r1;
			cin >> l1 >> r1;
			qr[i].l = l1;
			qr[i].r = r1;
			qr[i].id = i;
		}
		sort(qr + 1, qr + 1 + n, cmp);
		vector<int>left, index;
		for (int i = 1; i <= n; i++)
			left.push_back(qr[i].l), index.push_back(qr[i].id);
		if (qr[1].r >= qr[n].l)
		{
			cout << -1 << endl;
			go;
		}
		vector<int>v1, v2;
		int pos = 0;
		int i = 1;
		while (i <= n)
		{
			int pos = 0;
			int next_val = qr[i].r;
			int maxi = next_val;
			int next_pos = pos;
			int j = i;
			while (1)
			{
				int next = upper_bound(left.begin(), left.end(), next_val) - left.begin();
				int initial_maxi = maxi;
				while (next_pos < next)
					maxi = max(maxi, qr[j].r), j++, next_pos++;
				if (maxi > initial_maxi)
					next_val = maxi;
				else
				{
					break;
				}
			}
			if (v1.size() == 0)
			{
				while (pos < next_pos)
					v1.push_back(qr[i].id), i++, pos++;
			}
			else if (v2.size() == 0)
			{
				while (pos < next_pos)
					v2.push_back(qr[i].id), i++, pos++;
			}
			else
			{
				while (pos < next_pos)
					v1.push_back(qr[i].id), i++, pos++;
			}
		}
		if (v1.size() == 0 or v2.size() == 0)
		{
			cout << -1 << endl;
			go;
		}
		int ans[n + 1] = {0};
		for (int i = 0; i < v1.size(); i++)
			ans[v1[i]] = 1;
		for (int i = 0; i < v2.size(); i++)
			ans[v2[i]] = 2;
		for (int i = 1; i <= n; i++)
			cout << ans[i] << ' ';
		cout << endl;
	}
//.............................................. ٱلْحَمْدُ لِلَّٰ............................................
}